package com.example.lettcode._20240910;

/*
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
 */
public class Zui_chang_gong_gong_qian_zhui {

    public static void main(String[] args) {
        String[] strs = {"flower","flow","flight"};
        String s = longestCommonPrefix2(strs);
        System.out.println(s);
    }

    /**
     * 纵向求解
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            int currentLength = strs[i].length();
            if (currentLength < minLength) {
                minLength = currentLength;
            }
        }

        String sameResult = "";
        for (int i = 0; i < minLength; i++) {
            String sameStr = null;
            int sameCount = 0;
            for (int j = 0; j < strs.length; j++) {
                String str = strs[j];
                if (sameStr == null || "".equals(sameStr)) {
                    sameStr = String.valueOf(str.charAt(i));
                } else if (sameStr.equals(String.valueOf(str.charAt(i)))) {
                    sameCount++;
                }
            }
            if (sameCount != strs.length-1) {
                break;
            }
            sameResult = sameResult.concat(sameStr);
        }
        return sameResult;
    }

    /**
     * 横向求解
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        String prefix = strs[0];
        int arrayLength = strs.length;

        for (int i = 1; i < arrayLength; i++) {
            prefix = commonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                return prefix;
            }
        }
        return prefix;
    }

    private static String commonPrefix(String prefix, String nextStr) {
        int minLength = prefix.length() < nextStr.length() ? prefix.length() : nextStr.length();
        int n = 0;
        while (n < minLength) {
            if (prefix.charAt(n) != nextStr.charAt(n)) {
                break;
            }
            n++;
        }
        return nextStr.substring(0, n);
    }
}
